package TreeFormula;

import java.util.Scanner;
/**
 *
 * Exercise 9 (Part 2)
 * @author Katrin Baryshnikova
 */
public class BinaryTree {

    /**
     *  Узел дерева
     */
    static class Node {
        // левый и правый потомок

        Node left, right;
        // информация хранимая в узле
        Character token;
        // Является ли узел листом
        boolean leaf;

        /**
         * Конструктор
         * @param t задает токен
         * @param l true - лист
         */
        Node(Character t, boolean l) {
            token = t;
            left = null;
            right = null;
            leaf = l;
        }

        /**
         * 
         * @return возвращает символ хранмую в узле в виде строки
         */
        public String toString() {
            return token.toString();
        }
    }

    /**
     * Конструктор создает из входной строки дерево
     * @param s входная строка
     */
    public BinaryTree(String s) {
        Scanner input = new Scanner(new StringBuffer(s).reverse().toString());
        root = generateTree(input);
    }
    /**
     * root - корень дерева
     */
    private Node root = null;

    /**
     * Создает дерево из префиксной формы выражения
     * @param in - входной поток
     * @return возаращает сформированный узел
     */
    private Node generateTree(Scanner in) {
        Node node = null;
        boolean leaf = in.hasNextInt(); // проверяем является ли следующий символ числом
        if (leaf) {
            // Если он число, то считываем его 
            Integer a = in.nextInt();
            // и создаем новый узел, являющийся листом
            node = new Node(a.toString().charAt(0), leaf);
        } else {
            // иначе читаем следующую операцию
            String s = in.next();
            if (isSymbol(s.charAt(0))) {
                node = new Node(s.charAt(0), leaf);
            } else {
                // создаем новый узел хранящий эту операцию
                node = new Node(s.charAt(0), leaf);
                // рекурсивно вызываем процедуру для левого
                node.left = generateTree(in);
                // и правого потомка сформированного узла
                node.right = generateTree(in);
            }
        }
        return node;
    }

    /**
     * Выводит на печать в инфиксной форме
     */
    public void showInFix() {
        // обход начинаем с корня
        showInFix(root);
        System.out.println();
    }

    /**
     * Рекурсивно обходит дерево в префиксной и постфиксной позициях, 
     * и обрабатывает саму вершину 
     * @param x узел
     */
    private void showInFix(Node x) {
        // Если узел существует
        if (x != null) {
            // если узел не лист выводим открывающую скобку
            if (!x.leaf) {
                System.out.print("(");
            }
            // идем в правого потомка текущего узла
            showInFix(x.right);
            // выводим значение хранящееся в узле
            System.out.print(x + " ");
            // идем в левого потомка текущего узла
            showInFix(x.left);
            // если узел не лист выводим закрывающую скобку
            if (!x.leaf) {
                System.out.print(")");
            }
        }
    }

    /**
     * Выводим дерево в постфиксной форме
     */
    public void showPostfix() {
        showPostfix(root);
        System.out.println();
    }

    /**
     * Рекурсивно обходит дерево в постфиксной форме
     * @param x узел
     */
    private void showPostfix(Node x) {
        if (x != null) {
            showPostfix(x.left);
            showPostfix(x.right);
            System.out.print(x + " ");
        }
    }

    /**
     * Выводим дерево в префиксной форме
     */
    public void showPrefix() {
        showPrefix(root);
        System.out.println();
    }

    /**
     * Рекурсивно обходит дерево в префиксной форме
     * @param x 
     */
    private void showPrefix(Node x) {
        if (x != null) {
            System.out.print(x + " ");
            showPrefix(x.left);
            showPrefix(x.right);
        }
    }

    /**
     * Проверяет является ли символ буквой
     * @param c - символ
     * @return true - если c буква
     */
    private static boolean isSymbol(Character c) {
        return (int) c <= 122 && (int) c >= 97 ? true : false;
    }
}
